Biến đổi Fourier lượng tử là một phép biến đổi tuyến tính trên các qubit, phép biến đổi này tương tự như biến đổi Fourier rời rạc. Biến đổi Fourier lượng tử là một trong những thuật toán lượng tử quan trọng nhất, nó thường là một phần của các thuật toán lượng tử khác, đặc biệt là thuật toán Shor để phân tích thừa số nguyên tố và tính toán các logarit rời rạc.

Biến đổi Fourier lượng tử dựa trên thuật toán biến đổi Fourier nhanh của James Cooley và John Tukey. Nó có thể được thực hiện hiệu quả trên máy tính lượng tử, bởi nó có thể triệt tiêu các thành phần bằng cách nhân với các ma trận unita (áp dụng toán tử). Biến đổi Fourier lượng tử có thể được cài đặt và thực hiện trên một mạch lượng tử.

Thuật toán Deutsch-Jozsa

Trong bài toán Deutsch-Jozsa, ta có một hộp đen máy tính lượng tử thực thi một hàm. Đơn giản mà nói, nó nhận đầu vào là một giá trị nhị phân gồm n ký tự và trả về giá trị 0 hoặc 1. Coi như hàm f hoặc là bất biến (trả về 0 cho mọi đầu vào, hoặc trả về 1 cho mọi đầu vào) hoặc là cân bằng (trả về 0 cho 1 nửa số đầu vào, trả về 1 cho nửa còn lại); nhiệm vụ của chúng ta là xác định xem f là bất biến hay cân bằng dựa vào hộp đen[Tham khảo 4].

Thuật toán của Simon

Thuật toán của Simon giải quyết một vấn đề hộp đen theo hàm mũ nhanh hơn bất kì một thuật toán cổ điển nào, bao gồm những thuật toán xác suất chặn lỗi. Thuật toán này, đã đạt được một tốc độ với độ phức tạp[Tham khảo 5] theo hàm số mũ vượt qua tất cả các thuật toán cổ điển mà chúng ta cho là có hiệu quả, là động lực cho thuật toán phân tích thành thừa số của Shor.

Thuật toán của Shor

Thuật toán của Shor giải quyết các bài toán logarit rời rạc và bài toán phân tích thừa số nguyên trong thời gian đa thức (thời gian với độ phức tạp tính theo hàm đa thức), trong khi đó những thuật toán cổ điển nổi tiếng nhất tốn thời gian siêu đa thức (thời gian với độ phức tạp tính theo hàm siêu đa thức). Những bài toán này không được thuộc lớp P hoặc NP đầy đủ. Nó cũng đồng thời là một trong những thuật toán lượng tử giải quyết một vấn đề không phải hộp đen trong thời gian đa thức khi mà những thuật toán cổ điển nổi tiếng nhất chạy trong thời gian siêu đa thức.

Ước lượng các tổng Gauss

Một tổng Gauss là một loại tổng theo hàm số mũ. Thuật toán cổ điển nổi tiếng nhất về ước lượng những tổng này hoạt động với thời gian chạy theo hàm số mũ. Bởi vì vấn đề logarit rời rạc làm rút gọn phép ước lượng tổng Gauss nên một thuật toán cổ điển hiệu quả về việc ước lượng các tổng Gauss sẽ bao hàm một thuật toán cổ điển hiệu quả về tính toán logarit rời rạc, điều mà không chắc có được. Tuy nhiên, các máy tính lượng tử có thể ước lượng các tổng Gauss đển độ chính xác đa thức trong thời gian đa thức.

Bài toán cân cá và kiểm tra Fourier

Chúng ta có một máy oracle[Tham khảo 6] gồm có n hàm Boolean ngẫu nhiên ánh xạ n xâu bit nhị phân[Tham khảo 7] vào một giá trị Boolean. Chúng ta được yêu cầu tìm n xâu bit nhị phân z1, …, zn sao chovới phép biển đổi Hadamard – Fourier, ít nhất ¾ các xâu bit thỏa mãn.

| f ~ ( z i ) | ⩾ 1 {\displaystyle |{\tilde {f}}(z_{i})|\geqslant 1}

Và ít nhất ¼ thỏa mãn

| f ~ ( z i ) | ⩾ 2 {\displaystyle |{\tilde {f}}(z_{i})|\geqslant 2}

Điều này có thể thực hiện bởi thuật toán xác suất chặn lỗi.